Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs

摘要

The maximum clique problem is a well known NP-Hard problem with applicationsin data mining, network analysis, informatics, and many other areas. Althoughthere exist several algorithms with acceptable runtimes for certain classes ofgraphs, many of them are infeasible for massive graphs. We present a new exactalgorithm that employs novel pruning techniques to very quickly find maximumcliques in large sparse graphs. Extensive experiments on several types ofsynthetic and real-world graphs show that our new algorithm is up to severalorders of magnitude faster than existing algorithms for most instances. We alsopresent a heuristic variant that runs orders of magnitude faster than the exactalgorithm, while providing optimal or near-optimal solutions.